// 队列
function Queue() {
    // 队列数据
    this.items = []

    // enqueue(element)：向队列尾部添加一个（或多个）新的项。
    Queue.prototype.enqueue = function (element) {
        this.items.push(element)
    }

    // dequeue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。
    Queue.prototype.dequeue = function () {
        return this.items.shift()
    }

    // front()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。
    Queue.prototype.front = function () {
        return this.items[0]
    }

    // isEmpty()：如果队列中不包含任何元素，返回true，否则返回false。
    Queue.prototype.isEmpty = function () {
        return this.items.length == 0
    }

    // size()：返回队列包含的元素个数，与数组的length属性类似。
    Queue.prototype.size = function () {
        return this.items.length
    }
}


function Graph() {
    // 属性：顶点(数组)/边(字典)

    this.vertexes = [] //顶点
    this.edges = new Map() // 边

    // 方法
    // 添加顶点的方法
    Graph.prototype.addVertex = function (v) {
        this.vertexes.push(v);
        this.edges.set(v, [])
    }

    // 添加边的方法
    Graph.prototype.addEdges = function (v1, v2) {
        // 设置无向图
        this.edges.get(v1).push(v2);
        this.edges.get(v2).push(v1);
    }

    // toString
    Graph.prototype.toString = function () {
        var resultStr = '';
        for (var i = 0; i < this.vertexes.length; i++) {
            resultStr += this.vertexes[i] + '->';
            var edge = this.edges.get(this.vertexes[i]);
            for (var j = 0; j < edge.length; j++) {
                resultStr += edge[j] + ' ';
            }
            resultStr += '\n';
        }

        return resultStr;
    }

    // 初始化状态颜色
    Graph.prototype.initializeColor = function () {
        var colors = {};
        for (var i = 0; i < this.vertexes.length; i++) {
            colors[this.vertexes[i]] = 'white';
        }
        return colors;
    }


    // BFS广度优先搜索
    Graph.prototype.bfs = function (initV, handler) {

        // 获取所有顶点的颜色
        var colors = this.initializeColor();

        // 创建一个队列
        var queue = new Queue();
        queue.enqueue(initV);
        // 将initV变灰
        colors[initV] = 'gray';

        while (!queue.isEmpty()) {
            var v = queue.dequeue();
            // 取出v相连的顶点 vList是个数组
            var vList = this.edges.get(v);
            for (var i = 0; i < vList.length; i++) {
                var a = vList[i];
                if (colors[a] === 'white') {
                    colors[a] = 'gray';
                    queue.enqueue(vList[i]);
                }
                
            }
            // 因为v已经探测完毕, 将qv设置成黑色
            colors[v] = 'black';

            // 处理v
            if (handler) {
                handler(v);
            }
        }

    }


    // DFS 深度优先搜索
    Graph.prototype.dfs = function (initV, handler) {
        var colors = this.initializeColor();
        this.dfsVisit(initV, colors, handler);
    }

    // 递归调用的dfs
    Graph.prototype.dfsVisit = function (v, colors, handler) {
        // 将v变灰
        colors[v] = 'gray';
        // handler处理v
        handler(v);

        // 递归遍历v相邻的顶点
        var vList = this.edges.get(v);
        for (var i = 0; i < vList.length; i++) {
            // 如果是白色就递归寻找
            if (colors[vList[i]] === 'white') {
                this.dfsVisit(vList[i], colors, handler);
            }
        }

        // 将颜色变黑
        colors[v] = 'black';
    }
}
